package practise.alogrithm.hundredInterviewQuestions;

/**
 * find out the number that it appears time more than half number of array
 */
public class NumberMoreThanHalf {
    public static int findOutNumberMoreThanHalf(int[] array){
        int time=0;
        int number =0;
        for(int i: array){
            if(number!=i){
                if(time==0)
                    number=i;
                else{
                    time--;
                }
            }
            if(number==i){
                time++;
            }
        }
        if(time>array.length/2){
            return number;
        }
        time=0;
        for(int i:array){
            if(time>array.length/2){
                return number;
            }
            if(i==number){
                time++;
            }
        }
        return 0;
    }

    public static void main(String[] args){
        System.out.println("Result:" + findOutNumberMoreThanHalf(new int[]{1,2,3,1,1,2,1,3,1,1,4,2}));
    }
}
